﻿#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<string>
using namespace std;
int massage(vector<int>& nums) {
	int n = nums.size();
	if (n == 0) return 0;
	vector<int> f(n), g(n);
	f[0] = nums[0], g[0] = 0;
	for (int i = 1; i < n; i++)
	{
		f[i] = g[i - 1] + nums[i];
		g[i] = max(g[i - 1], f[i - 1]);
	}
	return max(f[n - 1], g[n - 1]);
}
int _rob(vector<int>& nums, int left, int right) {
	int n = nums.size();
	vector<int> f(n), g(n);
	f[left] = nums[left], g[left] = 0;
	for (int i = left + 1; i <=right; i++)
	{
		f[i] = g[i - 1] + nums[i];
		g[i] = max(g[i - 1], f[i - 1]);
	}
	return max(f[right], g[right]);
}
int rob(vector<int>& nums) {
	int n = nums.size();
	int x = nums[0] + _rob(nums, 2, n - 2);
	int y = _rob(nums, 1, n - 1);
	return max(x, y);
}
int deleteAndEarn(vector<int>& nums) {
	const int n = 10001;
	int arr[n];
	for (auto& e : nums)
		arr[e] += e;
	int f[n], g[n];
	f[0] = g[0] = 0;
	for (int i = 1; i < n; i++)
	{
		f[i] = g[i - 1] + nums[i];
		g[i] = max(f[i - 1], g[i - 1]);
	}
	return max(f[n - 1], g[n - 1]);
}
int minCost(vector<vector<int>>& costs) {
	int n = costs.size();
	vector<vector<int>> dp(n, vector<int>(3));
	dp[0][0] = costs[0][0], dp[0][1] = costs[0][1], 
	dp[0][2] = costs[0][2];
	for (int i = 1; i < n; i++)
	{
		dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + costs[i][0];
		dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + costs[i][1];
		dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + costs[i][2];
	}
	return min(dp[n - 1][0], min(dp[n - 1][1], dp[n - 1][2]));
}
int maxProfit(vector<int>& prices) {
	int n = prices.size();
	vector<vector<int>> dp(n, vector<int>(n));
	dp[0][0] = -prices[0];
	for (int i = 1; i < n; i++)
	{
		dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
		dp[i][1] = max(dp[i - 1][1], dp[i - 1][2]);
		dp[i][2] = dp[i - 1][0] + prices[i];
	}
	return max(dp[n - 1][1], dp[n - 1][2]);
}
int maxProfit(vector<int>& prices, int fee) {
	int n = prices.size();
	vector<int> f(n), g(n);
	f[0] = -prices[0];
	for (int i = 1; i < n; i++)
	{
		f[i] = max(f[i - 1], g[i - 1] - prices[i]);
		g[i] = max(g[i - 1], f[i - 1] + prices[i] - fee);
	}
	return g[n - 1];
}
int maxProfit(vector<int>& prices) {
	const int INF = 0x3f3f3f3f;
	int n = prices.size();
	vector<vector<int>> f(n, vector<int>(3,-INF));
	auto g = f;
	f[0][0] = -prices[0];
	for (int i = 1; i < n; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);
			g[i][j] = g[i - 1][j];
			if (j - 1 >= 0)// 如果该状态存在
				g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);
		}
	}
	// 找到最后⼀⾏的最⼤值
	return max(g[n - 1][0], max(g[n - 1][1], g[n - 1][2]));
}
int maxProfit(int k, vector<int>& prices) {
	const int INF = 0x3f3f3f3f;
	int n = prices.size();
	k = min(k, n / 2);
	vector<vector<int>> f(n, vector<int>(k,-INF));
	auto g = f;
	f[0][0] = -prices[0], g[0][0] = 0;
	for (int i = 1; i < n; i++)
	{
		for (int j = 0; j < k; j++)
		{
			f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);
			g[i][j] = g[i - 1][j];
			if (j - 1 >= 0)
				g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);
		}
	}
	// 找到最后⼀⾏的最⼤值
	int ret = -INF;
	for (int i = 0; i < k; i++)
	{
		ret = max(ret, g[n - 1][i]);
	}
	return ret;
}
int main()
{

	return 0;
}
